# -*- coding: utf-8 -*-
# Python中默认的编码格式是 ASCII 格式，在没修改编码格式时无法正确打印汉字，所以在读取中文时会报错。

# 给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，
# 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
#
# 示例:
#
# 输入: [1,2,3,4]
# 输出: [24,12,8,6]
# 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
#
# 进阶：
# 你可以在常数空间复杂度内完成这个题目吗？
# （ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）


# 自己
def product_except_self(nums):
    s = []
    for i in range(0, len(nums)):
        t = 1
        l = nums[:i] + nums[i + 1:]             # 每次remove掉num[i]
        for k in l:
            t = t * k
        s.append(t)
    return s


# 乘积 进阶
def productExceptSelf(self, nums: List[int]) -> List[int]:
    length = len(nums)

    # L 和 R 分别表示左右两侧的乘积列表
    L, R, answer = [0] * length, [0] * length, [0] * length

    # L[i] 为索引 i 左侧所有元素的乘积
    # 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
    L[0] = 1
    for i in range(1, length):
        L[i] = nums[i - 1] * L[i - 1]

    # R[i] 为索引 i 右侧所有元素的乘积
    # 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
    R[length - 1] = 1
    for i in reversed(range(length - 1)):
        R[i] = nums[i + 1] * R[i + 1]

    # 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
    for i in range(length):
        answer[i] = L[i] * R[i]

    return answer






# 自己  以前
# def product_except_self(nums):
#     s = 1
#     for i in nums:
#         s = s * i
#
#     for i in range(0, len(nums)):       # 进阶完成
#         b = s / nums[i]
#         nums[i] = b
#
#     return nums



if __name__ == "__main__":
    nums = [1, 2, 3, 4]
    print(product_except_self(nums))
